#include "util.h"
#include "common_sort.h"

/*
插入排序时间复杂度
外层循环每次循环时，内层循环次数从i-1到0

T(n) = 1+2+3+...+(n-2)+(n-1) //等差数列
     = (n-1)*n / 2
	 = O(n^2)

*/

void InsertionSort::sort(std::vector<int>& vec) {
	int len = vec.size();

	for (int i = 1; i < len; ++i) {
		int temp = vec[i];
		int j = i;
		for (; j > 0 && vec[j - 1] >= temp; --j) {
			vec[j] = vec[j - 1];
		}
		vec[j] = temp;
	}
}

